#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N=400003;
int n,m; long long op[N];
vector<long long> alls;
int binary(long long x){
	int l=0,r=alls.size();
	while(l<r){
		int mid=(l+r)/2;
		(alls[mid]>=x)?(r=mid):(l=mid+1);
	}
	return r;
}
namespace SGT{
	struct Node{
		int l,r,cnt,add;
		long long sum1,sum2;
	}node[N*3];
	void update(int u,int x){
		node[u].add+=x;
		node[u].sum1+=(long long)x*node[u].sum2;
	}
	void push_up(int u){
		node[u].cnt =node[u*2].cnt +node[u*2+1].cnt ;
		node[u].sum1=node[u*2].sum1+node[u*2+1].sum1;
		node[u].sum2=node[u*2].sum2+node[u*2+1].sum2;
	}
	void push_down(int u){
		update(u*2  ,node[u].add);
		update(u*2+1,node[u].add);
		node[u].add=0;
	}
	void build(int u,int l,int r){
		node[u]={l,r,0,0,0,0};
		if(l<r){
			int mid=(l+r)/2;
			build(u*2  ,l,mid  );
			build(u*2+1,mid+1,r);
		}
	}
	void modify_act(int u,int k,int cnt,long long sum1,long long sum2){
		if(node[u].l==k&&node[u].r==k)
			node[u].add=0,node[u].cnt=cnt,node[u].sum1=sum1,node[u].sum2=sum2;
		else{
			int mid=(node[u].l+node[u].r)/2; push_down(u);
			modify_act(u*2+(k>mid),k,cnt,sum1,sum2); push_up(u);
		}
	}
	void modify_add(int u,int l,int r,int x){
		if(l>r) return ;
		if(node[u].l>=l&&node[u].r<=r) update(u,x);
		else{
			push_down(u);
			int mid=(node[u].l+node[u].r)/2;
			if(l<=mid) modify_add(u*2  ,l,r,x);
			if(r> mid) modify_add(u*2+1,l,r,x);
			push_up(u);
		}
	}
	int query_cnt(int u,int l,int r){
		if(l>r) return 0;
		if(node[u].l>=l&&node[u].r<=r) return node[u].cnt;
		int mid=(node[u].l+node[u].r)/2; push_down(u);
		if(r<=mid) return query_cnt(u*2  ,l,r);
		if(l> mid) return query_cnt(u*2+1,l,r);
		return query_cnt(u*2,l,r)+query_cnt(u*2+1,l,r);
	}
	long long query_a(int u,int l,int r){
		if(l>r) return 0;
		if(node[u].l>=l&&node[u].r<=r) return node[u].sum1;
		int mid=(node[u].l+node[u].r)/2; push_down(u);
		if(r<=mid) return query_a(u*2  ,l,r);
		if(l> mid) return query_a(u*2+1,l,r);
		return query_a(u*2,l,r)+query_a(u*2+1,l,r);
	}
	long long query_b(int u,int l,int r){
		if(l>r) return 0;
		if(node[u].l>=l&&node[u].r<=r) return node[u].sum2;
		int mid=(node[u].l+node[u].r)/2; push_down(u);
		if(r<=mid) return query_b(u*2  ,l,r);
		if(l> mid) return query_b(u*2+1,l,r);
		return query_b(u*2,l,r)+query_b(u*2+1,l,r);
	}
	int binary_cnt(int x){
		int cur=1,ans=0;
		if(x>node[1].cnt) return node[1].r+1;
		while(node[cur].l<node[cur].r){
			push_down(cur);
			if(ans+node[cur*2].cnt>=x) cur*=2;
			else ans+=node[cur*2].cnt,cur=cur*2+1;
		}
		return node[cur].l;
	}
}
int binary_l(){
	int l=2,r=(m+2)/2+1;
	while(l<r){
		int mid=(l+r)/2,s1=SGT::binary_cnt(mid),s2=SGT::binary_cnt(m-mid+2);
		(SGT::query_a(1,1,s1)<SGT::query_a(1,s2,alls.size()))?(r=mid):(l=mid+1);
	}
	return r;
}
int binary_r(){
	int l=(m+2)/2,r=m;
	while(l<r){
		int mid=(l+r+1)/2,s1=SGT::binary_cnt(mid),s2=SGT::binary_cnt(m-mid+2);
		(SGT::query_a(1,1,s1)<SGT::query_a(1,s2,alls.size()))?(l=mid):(r=mid-1);
	}
	return l;
}
template<typename T>
void read(T& x){
	char ch; x=0;
	do ch=getchar();
	while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9')
		x=x*10+(ch-'0'),ch=getchar();
}
void write(long long x){
	char a[24]; int n=0,i;
	while(x>0) a[++n]=x%10+'0',x/=10;
	if(!n) a[++n]='0';
	for(i=n;i>0;i--) putchar(a[i]);
	putchar('\n');
}
int main(){
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	int i,s1,s2,s3,s4; long long ans; read(n);
	for(i=1;i<=n;i++) read(op[i]);
	for(i=1;i<=n;i++)
		alls.push_back(op[i]);
	sort(alls.begin(),alls.end());
	alls.erase(unique(alls.begin(),alls.end()),alls.end());
	SGT::build(1,1,alls.size());
	for(i=1;i<=n;i++){
		s1=binary(op[i])+1,s2=SGT::query_cnt(1,s1,s1);
		if(!s2){
			s3=SGT::query_cnt(1,1,s1-1)+1;
			m++,SGT::modify_act(1,s1,1,s3*op[i],op[i]);
			SGT::modify_add(1,s1+1,alls.size(),1);
		}else{
			m--,SGT::modify_act(1,s1,0,0,0);
			SGT::modify_add(1,s1+1,alls.size(),-1);
		}
		if(!m){ puts("0"); continue; }
		s1=binary_l(),s2=binary_r();
		ans =SGT::query_a(1,1,alls.size())*2;
		ans-=SGT::query_b(1,1,alls.size())*(m+1);
		if(s1<=s2){
			s3=SGT::binary_cnt(s1),s4=SGT::binary_cnt(s2);
			ans+=SGT::query_b(1,1,s3-1)*(s2-s1+1);
			ans+=SGT::query_b(1,s3,s4)*(s2+1);
			ans-=SGT::query_a(1,s3,s4);
			swap(s1,s2),s1=m-s1+2,s2=m-s2+2;
			s3=SGT::binary_cnt(s1),s4=SGT::binary_cnt(s2);
			ans-=SGT::query_b(1,s4+1,alls.size())*(s2-s1+1);
			ans+=SGT::query_b(1,s3,s4)*(s1-1);
			ans-=SGT::query_a(1,s3,s4);
		}
		write(ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
